/**
 * 942.增减字符串匹配
 */
public class Exerciser4 {
    public int[] diStringMatch(String s) {
        // 贪：
        // 当前位置为 I 的时候，那么选择当前最小的数据
        // 当前位置为 D 的时候，那么选择当前最大的数据
        int n = s.length();
        int[] ret = new int[n + 1];
        int left = 0,right = n;
        for(int i = 0;i < n;i++) {
            if(s.charAt(i) == 'I') {
                ret[i] = left++;
            }else {
                ret[i] = right--;
            }
        }
        // 处理最后一个位置的数据
        ret[n] = left;
        return ret;
    }
}
